Maximum Depth of Binary Tree
問題概要
二分木の最大深さを求めよ、という問題
解法
二分木の最大深さを知るには最大深さに辿れるまでの特定のノードを知る必要がある code:solution.cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
vector<vector<int>> vec = {};
traverse(root, 0, vec);
return vec.size();
}
void traverse(TreeNode* root, int level, vector<vector<int>>& vec) {
if (!root) return;
if (level < vec.size()) {
vec.at(level).push_back(root->val);
} else {
vec.push_back({root->val});
};
traverse(root->left, level+1, vec);
traverse(root->right, level+1, vec);
}
};
code:solution.go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
return traverse(root, 0)
}
func traverse(node *TreeNode, cnt int) int {
if node == nil { return cnt }
l := traverse(node.Left, cnt+1)
r := traverse(node.Right, cnt+1)
if l > r { return l }
return r
}